#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();

        int tgt = 0;
        for (auto e : grid)
            for (auto i : e)
                if (i != -1)
                    tgt++;

        int ret = 0;
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };
        function<void(int, int, int)> dfs = [&](int r, int c, int path)->void
            {
                if (grid[r][c] == 2)
                {
                    if (path == tgt) ret++;
                    return;
                }
                grid[r][c] = -1;
                for (int i = 0; i < 4; i++)
                {
                    int x = r + dx[i];
                    int y = c + dy[i];
                    if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] != -1)
                        dfs(x, y, path + 1);
                }
                grid[r][c] = 0;
            };

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    dfs(i, j, 1);
                    grid[i][j] = 1;
                    break;
                }
            }
        }
        return ret;
    }
};